#include <vector>

using namespace std;

class Solution {
public:
    int fa[90000];

    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

    // 这里加了返回值，当 x 和 y 不在一个集合里面时返回 false，否则返回 true
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
            return false;
        }
        return true;
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int count = 0;

        // 用 x 来代表每个位置的编号
        int x = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                x++;

                if (grid[i][j] == '0') {
                    continue;
                }

                // 只初始化 grid[i][j] 为 1 时的集合，节省时间
                fa[x] = x;

                // 这里用了点小技巧

                // 这里在遍历每个位置时，首先看看左侧是否为 1，
                // 如果是，那么将当前位置与左侧位置的编号合并，hasConnected 表示与左侧相连

                // 然后，看看上边是否为 1
                // 如果是，将当前位置与上边的位置的编号合并
                // 如果合并的返回值是 false，意思是说当前的位置与上边的位置并不在同一个集合

                // 再判断一下 hasConnected 的值，
                // a. 如果为 true，则说明当前的位置其实是继承自左侧的位置
                //    那么我们可以通过这些前提，推断出其实左侧和上边不在同一个集合里面，
                //    现在我们将两个岛屿合并了之后，次数需要减 1
                // b. 如果为 false，那么只需要直接将编号合并即可

                // 如果我们最后发现，当前的岛屿既不和左边相连，又不和上边相连，则认为发现新的岛屿，次数加 1

                bool hasConnected = false;

                if (i > 0 && grid[i - 1][j] == '1') {
                    merge(x, x - n);
                    hasConnected = true;
                }

                if (j > 0 && grid[i][j - 1] == '1') {
                    if (!merge(x, x - 1) && hasConnected) {
                        count--;
                    }
                }

                if (fa[x] == x) {
                    count++;
                }
            }
        }

        return count;
    }
};